In many service businesses, providers need to allocate their resources, which typically consist of a finite number of resource slots, to their customers through either an appointment process or a booking process. For example, a physician's working schedule is a resource that consists of finite time slots. Patients normally need to make appointments by selecting available time slots to see their physicians. Such types of appointment scheduling is common for many service providers, including but are not limited to, primary or specialty clinics, hair solons, auto maintenance shops, consultants, technicians, instructors, telephone/cable/internet service providers. As another example, the passenger seats in an air flight are finite resources. Travelers typically need to book the seats (available slots) in advance through travel agencies or online. Similar slot booking is also common to many other service providers, such as movie theaters, sport arenas, test centers, hotels, exhibition halls, etc. In the following descriptions, a resource slot that has been allocated is also called a booked slot, or a busy slot, or a reserved slot, and these terms are used interchangeably. Similarly, an unallocated slot is also called an open slot, or an available slot, or a free slot, and these terms are used interchangeably.
Conventionally, when a customer makes a service request from a provider, the provider's resource database is searched to check if there are available slots that can serve the customer's request. Typically, the provider also asks the customer's preference of the resource slots. Four possible conditions may arise: (1) If the customer's preferred slots are available, then these slots are allocated to the customer; (2) If there are available slots that can serve the customer who has no preference on the slots, then usually the first match or arbitrarily chosen slots are allocated to the customer; (3) If there are available slots that can serve the customer, but none of them fits the customer's preference, then the customer can either accept the non-preferred slots or the customer's request is rejected; (4) If there are no available slots that can serve the customer, then the customer's request is rejected.
For example, when a patient tries to make an appointment with his/her physician, the scheduler first estimates how many time slots are needed for this appointment. Assume the appointment normally takes about 30 minutes, and one unit time slot is 15 minutes, then 2 consecutive time slots will be needed to accommodate this appointment. The scheduler then checks the physician's working schedule to see if there are available time slots (i.e. ≧30 minutes, or at least 2 consecutive unit slots). If there are no available slots, then the patient's appointment cannot be made (condition 4). If the patient has time preference, e.g. morning appointment, but all available slots are in the afternoon, then the patient has to accept the non-preferred time slots or the appointment cannot be made (condition 3). If there are available slots and the patient has no time preference, then usually the first matching or an arbitrarily chosen 30-minute time slots are allocated to the patient (condition 2). Finally, if the patient's preferred time slots are available, then these time slots are allocated to the patient (condition 1).
As another example, when a customer tries to book 3 seats on a flight, the booking system first checks all open seats on the flights. If there are less than 3 open seats, then the customer's request cannot be satisfied (condition 4). If there are at least 3 open seats but none of them meets the customer preference, e.g. 3 adjacent seats, then the customer has to either accept the non-preferred seats or skip the flight (condition 3). If there are at least 3 open seats and the customer has no seat preference, then the first matching or arbitrarily chosen 3 open seats are reserved for the customer (condition 2). Finally, if there are at least 3 open seats that meet the customer's preference, then they are reserved for the customer (condition 1).
The conventional resource allocation practice described above has an intrinsic limitation in efficiency due to the tendency of resource slot fragmentation. The fragmentation of resource slots, which means the open slots and busy slots are juxtaposed, can be caused by the reservation of preferred slots, or the cancellation of previously reserved slots, or both. As a result, the fragmented slots may become difficult to accommodate the customers' requests. Furthermore, the fragmented slots may also cause lower utilization rate of the resources. For example, a patient who needs a 30 minutes appointment may not be accepted despite the availability of 2 separated 15 minutes time slots. These separated time slots, if left unallocated, will be wasted. Similarly, a customer who prefers 3 adjacent seats in a flight may have to accept 3 separated seats, hoping to be able to change the seats at the gate or on the flight (note such requests usually add significant workload to the airline staff). On the other hand, if the customer decides to skip this flight, these 3 seats may be wasted if no other customers book them.
As described above, customer's preference is usually considered when allocating the resource slots. However, there are two issues that have been largely overlooked in the conventional resource allocation process. First, the provider lacks formal guidance on how to allocate the resource slots to minimize the fragmentation. Although it is possible that in some cases, a provider may intentionally encourage customers to pick certain resource slots (e.g., a clinical scheduler may only disclose some available time slots to but withhold other available time slots from a patient), there is no formal and quantitative assessment of each possible resource allocation option and its potential impact on the resource fragmentation status. Second, customer's preference is usually not binary (e.g., like or dislike). Instead, it is a continuous variable that spans the spectrum from highly like to highly dislike, with many intermediate preference levels (e.g. somehow preferred, neutral, less preferred, etc.). Moreover, a customer's decision on selecting resource slots may be affected by external factors other than his/her preference level. For example, due to the established physician-patient relationship, a patient who has slight preference of morning appointment may instead gladly accept (and may even prefer) an afternoon appointment, after being informed that choice may help clinic improve efficiency and reduce waiting time.
In view of the forgoing descriptions, the present invention provides a novel method that can optimize the resource allocation process, so that the customers' requests could be better served and the providers' resources could be better utilized.